import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;

public class SolveNQueens51 {

    public List<List<String>> solveNQueens(int n) {
        HashMap<Integer, String> map = getQueenMap(n);
        List<String> path = new ArrayList<>();
        List<List<String>> res = new ArrayList<>();
        backTracking(0,path,res,n,map);
        return res;
    }

    public void backTracking(int row,List<String> path,List<List<String>> res,int n,HashMap<Integer,String> all){
        if (row==n){
            res.add(new ArrayList<>(path));
            return;
        }
        for (int col = 0; col < n; col++) {
            if (check(path,row,col,n)){
                path.add(all.get(col));
                backTracking(row+1,path,res,n,all);
                path.remove(path.size()-1);
            }
        }
    }

    public boolean check(List<String> path,int row,int col,int n){
        //判断列
        int left= col-1;
        int right= col+1;
        for (int i = path.size() - 1; i >= 0; i--) {
            if (path.get(i).indexOf("Q")==col||(left>=0&&path.get(i).indexOf("Q")==left)||(right<n&&path.get(i).indexOf("Q")==right)){
                return false;
            }
            left--;
            right++;
        }
        return true;
    }

    public HashMap<Integer, String> getQueenMap(int n){
        HashMap<Integer, String> res = new HashMap<>();
       StringBuffer sb = new StringBuffer();
        for (int i = 0; i < n; i++) {
            sb = new StringBuffer();
            for (int j = 0; j <n ; j++) {
                if (i==j){
                    sb.append("Q");
                }else {
                    sb.append(".");
                }
            }
            res.put(i,sb.toString());
        }
        return res;
    }

    public static void main(String[] args) {
        SolveNQueens51 solveNQueens51 = new SolveNQueens51();
        solveNQueens51.solveNQueens(4);
    }
}
